package dtm;

import org.junit.jupiter.api.Test;
import tm.EnumDirection;
import tm.TMConfiguration;
import tm.TMRule;
import tm.Tape;

import java.util.*;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author haoly
 * @title TMWithSubroutinesTest
 * @date 2025/4/23 19:40
 * @description 支持子例程的图灵机测试类
 * -----------------------------------
 * 如何用标准DTM模拟拓展了子例程的图灵机？
 * 答：子程序功能在标准 DTM 中通过为每个调用点复制子程序的规则和状态，并精心连接状态转换来模拟，无需额外的硬件或机制。
 *
 * -------------------------------------------------
 * 示例：给一个数加3
 * “给一个数加 3”这个任务可以分解为连续执行三次“给数加 1”的操作。
 * 我们可以将“给数加 1”（增量操作）看作一个**子例程**。
 * 这个子例程本身有一套规则，可以在纸带上找到一个二进制数并对其进行增量。
 *
 * 现在，想象我们要构建一个“加 3”的 DTM。使用子例程的直观想法是：
 * 1.  调用“增量”子例程。
 * 2.  调用“增量”子例程。
 * 3.  调用“增量”子例程。
 *
 * 但是，标准的 DTM 没有内建的“调用”和“返回”机制（没有堆栈来存储返回地址）。为了模拟这个过程，标准 DTM 采用的是**复制**的方法，并利用**状态的序列**来跟踪任务的进展和子例程的返回位置。
 *
 * 模拟过程是这样实现的：
 *
 * 1.  **定义主任务的状态序列：** 我们用一系列状态来表示“加 3”这个主任务的进展：
 *     * `added_zero` (状态 0): 表示已经加了 0，准备进行第一次增量。这是初始状态。
 *     * `added_one` (状态 1): 表示已经加了 1，准备进行第二次增量。这是第一次增量完成后应该“返回”的状态。
 *     * `added_two` (状态 2): 表示已经加了 2，准备进行第三次增量。这是第二次增量完成后应该“返回”的状态。
 *     * `added_three` (状态 3): 表示已经加了 3，任务完成。这是第三次增量完成后应该“返回”的状态，也是接受状态。
 *
 * 2.  **复制子例程规则并连接状态：** 我们为“增量”子例程创建**三个独立的规则副本**，每个副本对应主任务中的一次调用。
 * 这些副本通过将子例程的**返回状态 (return_state)** 参数设置为正确的主任务状态来实现连接：
 *     * **第一次调用模拟：** 生成一套“增量”规则，其起始状态是 `added_zero`，结束状态（即子例程完成时转换到的状态）是 `added_one`。这模拟了从状态 `added_zero` 调用增量，完成后回到状态 `added_one`。
 *     * **第二次调用模拟：** 生成**另一套独立的**“增量”规则副本，其起始状态是 `added_one`，结束状态是 `added_two`。这模拟了从状态 `added_one` 调用增量，完成后回到状态 `added_two`。
 *     * **第三次调用模拟：** 生成**第三套独立的**“增量”规则副本，其起始状态是 `added_two`，结束状态是 `added_three`。这模拟了从状态 `added_two` 调用增量，完成后回到状态 `added_three`。
 *
 * 3.  **构建完整的规则簿：** 将这三套（共 3 * 6 = 18 条）独立的增量规则合并到一个大的规则簿中，这就是“加 3”这个 DTM 的完整规则簿。
 *
 * 4.  **执行流程：**
 *     * 机器从初始状态 `added_zero` 开始。它遵循**第一套**增量规则。
 *     * 当第一套增量规则执行完毕（找到空白符 `_` 并向左移动一步）时，根据这套规则的定义，机器的状态会自动转换到 `added_one`。
 *     * 现在机器处于状态 `added_one`，它开始遵循**第二套**增量规则（因为这套规则的起始状态是 `added_one`）。
 *     * 当第二套增量规则执行完毕时，根据其定义，机器状态转换到 `added_two`。
 *     * 最后，机器处于状态 `added_two`，遵循**第三套**增量规则。
 *     * 当第三套增量规则执行完毕时，机器状态转换到 `added_three`。由于 `added_three` 是接受状态，机器停止并接受。
 *
 * 通过这种方式，标准 DTM 模拟了连续三次调用子例程的过程，而无需真实的调用堆栈或返回地址。每一次“子例程调用”实际上都是执行一套专门为此调用点配置的、独立的规则副本。
 * 子例程完成后的“返回”则是硬编码在规则中，即转换到预定的下一个主任务状态。
 *
 * 这种方法虽然导致规则簿变大（因为需要复制），但证明了标准 DTM 具有实现子例程功能的模拟能力。
 */
public class TMWithSubroutinesTest {

    @Test
    public void testRun(){
        Integer addedZero = 0;
        Integer addedOne = 1;
        Integer addedTwo = 2;
        Integer addedThree = 3;

        List<TMRule<Object>> rules = new ArrayList<>(incrementRules(addedZero, addedOne));
        rules.addAll(incrementRules(addedOne, addedTwo));
        rules.addAll(incrementRules(addedTwo, addedThree));

        DTMRulebook<Object> rulebook = new DTMRulebook<>(rules);

        assertEquals(18, rulebook.getRules().size());

        char blankChar = '_';
        Tape tape = new Tape(List.of('1','0','1'), '1', List.of(), blankChar);

        System.out.println(tape);
        TMConfiguration<Object> configuration = new TMConfiguration<>(addedZero, tape);

        DTM<Object> dtm = new DTM<>(configuration, Set.of(addedThree), rulebook);
        dtm.run();

        System.out.println(dtm.getCurrentConfiguration().getTape());


    }

    private List<TMRule<Object>> incrementRules(Object startState, Object returnState) {
        Object incrementing = startState;
        Object finishing = new Object();
        Object finished = returnState;

        List<TMRule<Object>> rules = Arrays.asList(
                new TMRule<>(incrementing, '0', finishing, '1', EnumDirection.RIGHT),
                new TMRule<>(incrementing, '1', incrementing, '0', EnumDirection.LEFT),
                new TMRule<>(incrementing, '_', finishing, '1', EnumDirection.RIGHT),
                new TMRule<>(finishing, '0', finishing, '0', EnumDirection.RIGHT),
                new TMRule<>(finishing, '1', finishing, '1', EnumDirection.RIGHT),
                new TMRule<>(finishing, '_', finished, '_', EnumDirection.LEFT)

        );

        return new ArrayList<>(rules);
    }
}
